Algebraic normal form

In Boolean logic, the algebraic normal form (ANF) is a method of standardizing and normalizing logical formulas. As a normal form, it can be used in automated theorem proving (ATP), but is more commonly used in the design of cryptographic random number generators, specifically linear feedback shift registers (LFSRs). A logical formula is considered to be in ANF if and only if it is a single algebraic sum (XOR) of a constant a_0 and one or more conjunctions of the function arguments. ANF is also known as "Zhegalkin polynomials" (Russian: полиномы Жегалкина) and as "Positive Polarity (or Parity) Reed-Muller" expression.

Putting a formula into ANF makes it easy to identify linear functions, as is needed for linear feedback in LFSRs: a linear function is one that is a sum of literals. Properties of nonlinear feedback shift registers can also be deduced from certain properties of the feedback function in ANF.

The general ANF can be written as:

f(x_1, x_2, \ldots, x_n) = \! a_0 %2B \!
a_1x_1 %2B a_2x_2 %2B \cdots %2B a_nx_n %2B \!
a_{1,2}x_1x_2 %2B \cdots %2B a_{n-1,n}x_{n-1}x_n %2B \!
\cdots %2B \!
a_{1,2,\ldots,n}x_1x_2\ldots x_n \!

where a_0, a_1, \ldots, a_{1,2,\ldots,n} \in \{0,1\}^* fully describes f.

For each function f there is a unique ANF. There are only four functions with one argument: f(x)=0, f(x)=1, f(x)=x, f(x)=1 %2B x (all of them are given in the ANF). To represent a function with multiple arguments one can use the following equality: f(x_1,x_2,\ldots,x_n) = g(x_2,\ldots,x_n) %2B x_1 h(x_2,\ldots,x_n), where g(x_2,\ldots,x_n) = f(0,x_2,\ldots,x_n) and h(x_2,\ldots,x_n) = f(0,x_2,\ldots,x_n) %2B f(1,x_2,\ldots,x_n). Indeed, if x_1=0 then x_1 h = 0 and so f(0,\ldots) = f(0,\ldots); if x_1=1 then x_1 h = h and so f(1,\ldots) = f(0,\ldots) %2B f(0,\ldots) %2B f(1,\ldots). Since both g and h have less arguments than f it follows that using this process recursively we will finish with functions with one variable. For example, let us construct ANF of f(x,y)= x \lor y (logical or): f(x,y) = f(0,y) %2B x(f(0,y)%2Bf(1,y)); since f(0,y)=0 \lor y = y and f(1,y)=1 \lor y = 1, it follows that f(x,y) = y %2B x (y %2B 1); by opening the parentheses we get the final ANF: f(x,y) = y %2B x y %2B x = x %2B y %2B x y.

See also